/**************************************************************************
 * artic.c
 *
 * CECS619 Project 3
 *
 * Authors: Max Stoler, Jason Hatton
 * 
 *************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "subgraph.h"

/************************TYPES********************************************/

typedef struct SUB_GRAPH_DATA_T
{
	Graph *g;
	int numSubGraphs;
	int *biggestGraph;
	int biggestSize;
} SubGraph;

/************************PROTOTYPES***************************************/

static void Enumerate(SubGraph *s, int *v, int d, int i,
                      int graphSize, int numVerts);
static int isSubGraph(SubGraph *s, int *v, int size);


/************************FUNCTIONS****************************************/





/**************************************************************************
 * FindSubGraphs
 *
 * All of the subgraphs in g will be counted. The number of subgraphs will
 * be displayed along with the vertex names of the largest subgraph.
 * g - A pointer to a graph.
 *************************************************************************/
void FindSubGraphs(Graph *g)
{
	/*Setup a sub graph object*/
	SubGraph subGraph;
	int i;
	int *v;

	subGraph.g = g;
	subGraph.numSubGraphs = 0;
	subGraph.biggestGraph = (int*)malloc(sizeof(int)*g->size);
	if(!subGraph.biggestGraph)
	{
		printf("Out of memory!\n");
		exit(1);
	}
	subGraph.biggestSize = 0;

	v = (int*)malloc(sizeof(int)*g->size);
	if(!v)
	{
		printf("Out of memory!\n");
		exit(1);
	}

	/*Enumerate all subgraphs of size 2 through g->size*/
	for(i=2; i<=g->size; i++)
		Enumerate(&subGraph, v, 0, 0, i, g->size);

	/* Print output*/
	printf("Number of sub graphs: %d\n", subGraph.numSubGraphs);
	printf("Biggest sub graph: \n");
	for(i=0; i<subGraph.biggestSize; i++)
		printf("%2d | %s\n", subGraph.biggestGraph[i],
		                     g->vertexNames[subGraph.biggestGraph[i]]);

	free(subGraph.biggestGraph);
	free(v);
	return;
}

/**************************************************************************
 * Enumerate
 *
 * Enumerate all sub graphs of a given size and count them. The largest
 * sub graph will also be stored.
 *
 * s - A subgraph object that stores information about all the found
 *     subgraphs.
 * v - an array that stores the working set of vertices to enumerate.
 * d - The recursive depth or the current vertex position we are looking at.
 * i - The current vertex to enumerate. Only vertices between i and numVerts
 *     are available for enumeration.
 * graphSize - The size of the subgraphs to find.
 * numVerts - The number of vertices available to enumerate.
 *************************************************************************/
static void Enumerate(SubGraph *s, int *v, int d, int i,
                      int graphSize, int numVerts)
{
	int j;
	int max;
	/*See if we have enumerated a set of vertices*/
	if(d >= graphSize)
	{
		if(isSubGraph(s,v,graphSize))
		{
			s->numSubGraphs++;

			/*Save the largest subgraph*/
			if(graphSize > s->biggestSize)
			{
				memcpy(s->biggestGraph, v, sizeof(int)*graphSize);
				s->biggestSize = graphSize;
			}
			/*
			for(j=0; j<graphSize; j++)
			{
				printf("%2d ", v[j]);
			}
			printf("\n");
			*/
		}
		return;
	}

	/*Calculate the maximum vertex to enumerate*/
	max = d + numVerts - graphSize;

	/*Enumerate all available vertices.*/
	for(j=i; j<=max; j++)
	{
		v[d] = j;
		Enumerate(s, v, d+1, j+1, graphSize, numVerts);
	}
}

/**************************************************************************
 * isSubGraph
 *
 * See if this is a fully connected sub graph or not.
 *
 * s - A pointer to the subgraph object.
 * v - a pointer to a set of vertices to evaluate.
 * size - The number of vertices in v.
 *************************************************************************/
static int isSubGraph(SubGraph *s, int *v, int size)
{
	int i;
	int j;
	int adj;
	for(i=0; i<size; i++)
	{
		for(j=i+1; j<size; j++)
		{
			adj = GraphGetAdj(s->g, v[i], v[j]);
			if(!adj)
				return 0;
		}
	}
	return 1;
}



